package com.example.tree.segmenttree;

/**
 * 给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。
 * 请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：
 *  在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
 *
 *  答案保证在 32 位有符号整数以内。
 *
 *  示例 1：
 *
 *  输入：target = [1,2,3,2,1]
 * 输出：3
 * 解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
 * [0,0,0,0,0] 将下标为 0 到 的元素（包含二者）加 1 。
 * [1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
 * [1,2,2,2,1] 将下表为 2 的元素增加 1 。
 * [1,2,3,2,1] 得到了目标数组。
 *
 *
 *  示例 2：
 *
 *  输入：target = [3,1,1,2]
 * 输出：4
 * 解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (tar
 * get) 。
 *
 *  示例 3：
 *
 *  输入：target = [3,1,5,4,2]
 * 输出：7
 * 解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
 *                                   -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2]
 *  -> [3,1,5,4,2] (target)。
 *
 *
 *  示例 4：
 *
 *  输入：target = [1,1,1,1]
 * 输出：1
 *
 *  提示：
 *  1 <= target.length <= 10^5
 *  1 <= target[i] <= 10^5
 */
public class Leetcode1526_MinNumberOperations {

    public static void main(String[] args) {
        int[] nums = {3,1,5,4,2};
        System.out.println(minNumberOperations2(nums));
    }

    /**
     * 最优解:差分数组
     *
     * @param target
     * @return
     */
    public static int minNumberOperations2(int[] target) {
        int res = target[0];
        for (int i = 1; i < target.length; i++) {
            res += Math.max(target[i] - target[i - 1], 0);
        }
        return res;
    }

    /**
     * 解法一:线段树
     *
     * @param target
     * @return
     */
    public static int minNumberOperations1(int[] target) {
        int n = target.length;
        SegTree st = new SegTree(n, target);
        return st.rec(0, 0, n - 1);
    }


    static class SegTree { // 定义线段树，采⽤用数组存储
        int[] value, nums;
        int n;// 表示nums数组的⻓长度

        SegTree(int n, int[] nums) {
            value = new int[4 * n];
            this.n = n;
            this.nums = nums;
            build(1, 0, n - 1);//注意bulid pos的初值是1 后序的坐标也要跟着变
        }

        public void build(int pos, int left, int right) {// pos表示最小值坐标在value中存储的位置
            if (right == left) {
                value[pos] = left;
                return;
            }// 注意存储的是坐标
            build(2 * pos, left, (left + right) / 2);// 建立左子树
            build(2 * pos + 1, (right + left) / 2 + 1, right);// 建立右子树
            value[pos] = nums[value[2 * pos]] > nums[value[2 * pos + 1]] ? value[2 * pos + 1] : value[2 * pos];
        }

        // pos 为nums[left,right]最小值的坐标在value中存储的位置
        int query(int pos, int qleft, int qright, int left, int right) {// 递归的找到给定区间的最小值

            if (left > right)
                return -1;
            if (qright == right && qleft == left)
                return value[pos];// 递归出口
            int mid = (qright + qleft) / 2;
            int leftIndex = query(2 * pos, qleft, mid, left, Math.min(mid, right));//左侧区间最小值的坐标
            int rightIndex = query(2 * pos + 1, mid + 1, qright, Math.max(left, mid + 1), right);

            if (leftIndex == -1)
                return rightIndex;
            if (rightIndex == -1)
                return leftIndex;

            return nums[leftIndex] > nums[rightIndex] ? rightIndex : leftIndex;
        }

        int rec(int od, int l, int r) {// 分别对左右子区间递归累加直⾄至区间最小值本题定制函数
            if (l > r) return 0;
            int m = query(1, 0, n - 1, l, r);
            return nums[m] - od + rec(nums[m], l, m - 1) + rec(nums[m], m + 1, r);
        }
    }
}
